The present application relates to networking and more particularly to techniques for determining a local repair path using Constraint Shortest Path First (CSPF) techniques.
Connection-oriented protocols are widely used to transport data across computer networks. In a connection-oriented protocol, a connection is set up between two endpoints in a network, usually prior to data transmission. Nodes or network devices at the end points of a connection use a preliminary protocol to establish an end-to-end path traversed by the connection before any data is sent. A connection is then signaled using the established path. The preconfigured connection with its associated path is then used to transport data between the end points. The first network device in the path is referred to as an ingress network device (e.g., an ingress router) and the last network device in the path is referred to as an egress network device (e.g., an egress router). Examples of connection-oriented mechanisms include circuit switching protocols such as Asynchronous Transfer Mode (ATM) protocol, frame relay, Multi-Protocol Label Switching (MPLS), and others.
Multi-Protocol Label Switching (MPLS) (also referred to as “tag switching” or “label switching” protocol) is a data-carrying mechanism which emulates some properties of a circuit-switched network over a packet-switched network. It was designed to provide a unified data-carrying service for both circuit-based clients and packet-switching clients which provide a datagram service model. It can be used to carry many different kinds of traffic, including IP packets, as well as native ATM, SONET, and Ethernet frames. In MPLS, a connection between two end points is referred to as a Label Switched Path (LSP). Various signaling protocols such as Label Distribution Protocol (LDP), Resource Reservation Protocol—Traffic Engine (RSVP-TE), Constraint-based Routed LDP (CR-LDP) and others may be used to set up an LSP. Routers in an MPLS LSP are referred to as Label Switching Routers (LSRs). The first router in an LSP is referred to as an ingress edge router and the last router in an LSP is referred to as the egress edge router. Routers in between the ingress router and the egress router are referred to as transit LSRs. LSPs are unidirectional and enable a packet to be label switched through the MPLS network from one endpoint to another.
A connection, such as an LSP in an MPLS network, may experience data transmission disruptions due to failures of one or more nodes and/or links in the path traversed by the connection. In order to safeguard against such disruptions along the original preconfigured connection, one or more alternate connections are generally computed for the original connection that enable failure points (e.g., failed links or nodes) along the path of the original connection to be bypassed. These alternate connections are referred to as “local repair connections”. Each local repair connection has an associated path (referred to as a local repair path) that originates at a start node in the path associated with the original connection and ends at an end node in the path associated with the original connection that is downstream from the start node. Different protocols may use different techniques to set up and maintain local repair connections. For example, for MPLS, RFC 4090 describes techniques to establish local repair LSPs (e.g., backup LSPs or detour LSPs) for local repair of LSP tunnels.
A connection is said to be protected if at least one local repair connection has been set up for that connection. A node or link in a connection is said to be protected if at least one local repair connection has been configured that does not use that node or link.
Various different techniques may be used for determining a path for a local repair connection. For example, Constraint Shortest Path First (CSPF) techniques may be used to determine a path for a local repair connection. CSPF is a type of shortest path first algorithm that computes an optimal path from a start node to an end node satisfying a set of constraints. The constraints may include end-to-end delay, maximum numbers of links/nodes traversed, maximum bandwidth required per link, costs associated with the links, and the like. An example of a CSPF technique is the Dijkstra algorithm. CSPF is widely used in MPLS. The path computed using CSPF may be the same as the path computed using a shortest path first algorithm (without constraints) or may be completely different depending on the constraints to be satisfied.
Improved techniques are desired for computing paths for local repair connections using CSPF or CSPF-like techniques.